package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * 成员变量next存放个临时值, 用于hasNext,next和初始化, 小技巧!
 * 递归问题
 *
 * @author tzp
 * @since 2020/10/23
 */
public class LC341 implements TreeProblem {
    public interface NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }

    static class NestedIterator implements Iterator<Integer> {
        LinkedList<NestedInteger> s1 = new LinkedList<>();
        LinkedList<Integer> s2 = new LinkedList<>();
        Integer next = null;

        public NestedIterator(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) return;
            NestedInteger dummy = new NestedInteger() {
                @Override
                public boolean isInteger() {
                    return false;
                }

                @Override
                public Integer getInteger() {
                    return null;
                }

                @Override
                public List<NestedInteger> getList() {
                    return nestedList;
                }
            };
            s1.offerLast(dummy);
            s2.offerLast(0);
            next = pushRGetOne();
        }

        @Override
        public Integer next() {
            Integer result = next;
            next = pushRGetOne();
            return result;
        }

        private Integer pushRGetOne() {//只有list类型的才放入栈中.
            if (s1.size() == 0) return null;//无了
            List<NestedInteger> list = s1.peekLast().getList();
            Integer index = s2.pollLast();
            NestedInteger r = list.get(index);
            index++;
            if (index == list.size()) {
                s1.pollLast();
            } else {
                s2.offerLast(index);
            }//栈里最后一个元素的list里拿出一个元素

            if (r.isInteger()) {
                return r.getInteger();
            } else if (r.getList().size() == 0) {//是一个空list, 继续拿
                return pushRGetOne();
            } else {//非空list, 放入栈继续拿.
                s1.offerLast(r);
                s2.offerLast(0);
                return pushRGetOne();
            }
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }
    }


    public static void main(String[] args) {
        NestedInteger1 n1 = new NestedInteger1(1);
        NestedInteger1 n2 = new NestedInteger1(2);
        NestedInteger1 n3 = new NestedInteger1(3);
        NestedInteger1 n4 = new NestedInteger1(4);
        NestedInteger1 n5 = new NestedInteger1(5);
        NestedInteger1 n6 = new NestedInteger1(6);

        {
            NestedInteger2 l1 = new NestedInteger2(Arrays.asList(n1, n1));
            NestedIterator iterator = new NestedIterator(Arrays.asList(l1, n2, l1));
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
            System.out.println("---------");
        }

        {
            NestedInteger2 l3 = new NestedInteger2(Arrays.asList(n3, n4));
            NestedInteger2 l2 = new NestedInteger2(Arrays.asList(n2, l3));
            NestedIterator iterator1 = new NestedIterator(Arrays.asList(n1, l2));
            while (iterator1.hasNext()) {
                System.out.println(iterator1.next());
            }
            System.out.println("---------");
        }

        {
            //[[1,2],[3],[4,5,6]]
            NestedInteger2 ll1 = new NestedInteger2(Arrays.asList(n1, n2));
            NestedInteger2 ll2 = new NestedInteger2(Arrays.asList(n4, n5, n6));
            NestedInteger2 ll3 = new NestedInteger2(Arrays.asList(n3));

            NestedIterator iterator1 = new NestedIterator(Arrays.asList(ll1, ll3, ll2));
            while (iterator1.hasNext()) {
                System.out.println(iterator1.next());
            }
            System.out.println("---------");
        }
        {
            //[]
            NestedIterator iterator1 = new NestedIterator(Arrays.asList());
            while (iterator1.hasNext()) {
                System.out.println(iterator1.next());
            }
            System.out.println("---------");
        }
        {
            //[]
            NestedInteger2 nn = new NestedInteger2(Collections.emptyList());
            NestedIterator iterator1 = new NestedIterator(Arrays.asList(nn));
            while (iterator1.hasNext()) {
                System.out.println(iterator1.next());
            }
            System.out.println("---------");
        }
    }

    static class NestedInteger1 implements NestedInteger {
        int x;

        public NestedInteger1(int x) {
            this.x = x;
        }

        @Override
        public boolean isInteger() {
            return true;
        }

        @Override
        public Integer getInteger() {
            return x;
        }

        @Override
        public List<NestedInteger> getList() {
            return null;
        }
    }

    static class NestedInteger2 implements NestedInteger {
        List<NestedInteger> list;

        public NestedInteger2(List<NestedInteger> list) {
            this.list = list;
        }

        @Override
        public boolean isInteger() {
            return false;
        }

        @Override
        public Integer getInteger() {
            return null;
        }

        @Override
        public List<NestedInteger> getList() {
            return list;
        }
    }
}
